package com.iceph0x.algorithm.sort;

import java.util.Comparator;
import java.util.Random;

import com.iceph0x.algorithm.framework.ISort;

public class QuickSort implements ISort {
    
    Random r = new Random();

    @Override
    public void sort(int[] data) {
        if (data == null || data.length < 2)
            return;
        
        sort(data, 0, data.length - 1); 
    }
    
    private void sort(int[] data, int low, int high) {
        if (low >= high)
            return;

        int pivotIndex = partition(data, low, high);
        sort(data, low, pivotIndex - 1);
        sort(data, pivotIndex + 1, high);
    }
    
    private int partition(int[] data, int low, int high) {
        int pivot;
        int pivotIndex;
        if (high - low > 8) {
            swap(data, low, low + r.nextInt(high - low + 1));
        }
        pivotIndex = low++;
        pivot = data[pivotIndex];
        
        while (low < high) {
            while (data[low] <= pivot && low < high) 
                ++ low;
            while (low < high && data[high] > pivot)
                -- high;
            
            if (low < high)
                swap(data, low++, high--);
        }
        
        if (low == high && data[low] <= pivot) {
            swap(data, pivotIndex, low);
        }
        else {
            swap(data, pivotIndex, -- low);
        }
        return low;
    }
    
    private void swap(int[] data, int i, int j) {
        if (data[i] == data[j])
            return;
        
        data[i] ^= data[j];
        data[j] ^= data[i];
        data[i] ^= data[j];
    }


    @Override
    public void sort(Object[] data, Comparator<Object> c) {
        // TODO Auto-generated method stub

    }
}
